package com.hanxiaozhang.no10leetcode.string;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 〈一句话功能简述〉<br>
 * 〈给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。〉
 * <p>
 * 背lengthOfLongestSubstring2(String s)，滑动窗口思路 + 存储Map结构
 *
 * @author hanxinghua
 * @create 2022/12/30
 * @since 1.0.0
 */
public class No3LengthOfLongestSubstring {

    public static void main(String[] args) {

        String s = "abcabcbb";

        // charAt(int index)：返回指定索引位置的值
        System.out.println("charAt: " + s.charAt(2));

        // indexOf(int ch, int fromIndex)：用于从给定的fromIndex获取字符串中指定字符的索引，它从fromIndex接受一个字符，并返回其首次出现的索引；如果字符串中不存在该字符，则返回-1。
        System.out.println("indexOf(int ch, int fromIndex)： " + s.indexOf('a', 0));


        System.out.println(lengthOfLongestSubstring2(s));
    }

    /**
     * 自己的写法
     * <p>
     * 效率低，太长字符串LeetCode提交超时
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {


        char[] chars = s.toCharArray();
        // Tips：注意处理极值问题
        if (chars.length == 0) {
            return 0;
        }
        int length = 1;
        Set<Character> sets = new HashSet<>();
        // 循环i：模拟每次取几个元素 Tips：直接从2开始，因为最少子串长度是1
        for (int i = 2; i <= chars.length; i++) {
            // 循环j：滑动窗口，起始位置
            flag:
            for (int j = 0; j < chars.length; j++) {
                // 循环k：滑动窗口，起始位置
                for (int k = j; k < j + i; k++) {
                    if (k >= chars.length) {
                        continue;
                    }
                    sets.add(chars[k]);
                    // Tips：优化->同一个长度，发现一个，就停止循环
                    if (sets.size() == i) {
                        length = i;
                        break flag;
                    }
                }
                sets.clear();
            }
            sets.clear();
        }
        return length;
    }


    /**
     * 别人写法1
     * <p>
     * 遍历字符串，每次以i值记录，不回溯i值，用flag记录遍历过程找到的重复的字符的位置。
     * 如果遇到重复字符，i-flag，即为子串长度，此时flag重新定位到子串中重复字符的位置，i继续往后遍历。
     * 这里length跟result记录长度。
     * <p>
     * 问题：
     * indexOf(int ch, int fromIndex)，底层也是一个循环
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        // flag记录遍历过程找到的重复的字符的位置
        int flag = 0;
        // 遍历字符串，每次以 i 值记录，不回溯 i 值
        int i = 0;
        // 当前字符串长度
        int length = 0;
        // 最终结果
        int result = 0;
        while (i < s.length()) {
            // s.charAt(i) -> 获取i位置的字符。
            // s.indexOf(s.charAt(i), flag) -> i位置的字符，从开始位置索引位置（flag）寻找，返回首次出现的位置索引
            int pos = s.indexOf(s.charAt(i), flag);
            // 如果i > pos 时，即准备新加入的字符，在原来子串上存在重复。
            if (i > pos) {
                // 子串长度大于结果长度，更新结果长度
                if (length > result) {
                    result = length;
                }
                //  "字符串长度 - 首次出现重复的字符的位置 - 1"的值,小于等于结果result时，直接返回结果，即剩余元素的子串比当前记录的结果小，没有必要比较了。
                if (result >= s.length() - pos - 1) {
                    return result;
                }
                // 子串长度 = i - pos - 1;
                length = i - pos - 1;
                // 修改重复元素的位置
                flag = pos + 1;
            }
            length++;
            i++;
        }
        return length;
    }


    /**
     * 别人写法2
     * 标签：滑动窗口 -> [窗口的开始位置,窗口的结束位置] -> 即[start, end]
     *
     * <p>
     * 暴力解法时间复杂度较高，会达到O(n2)，故而采取滑动窗口的方法降低时间复杂度。
     * 定义一个MAP数据结构：key：字符，value：字符位置+1，其中加1，表示从字符位置后一个才开始不重复。
     * 我们定义不重复子串的开始位置为start，结束位置为end，
     * 随着end不断遍历向后，会遇到与[start, end]区间内字符相同的情况，此时将字符作为key值，获取其value值，
     * 并更新start，此时[start, end]区间内不存在重复字符。 无论是否更新start，都会更新其map数据结构和结果result。
     * <p>
     * 时间复杂度：O(n)
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring2(String s) {
        int n = s.length(), result = 0;
        // key -> 字符，value -> 字符位置+1，加1，表示从字符位置后一个才开始不重复。
        Map<Character, Integer> map = new HashMap<>(8);
        // 模拟窗口
        for (int end = 0, start = 0; end < n; end++) {
            // 1. 获取当前位置（end）的字符
            char alpha = s.charAt(end);
            // 2. 判断map中是否包含该字符，如何包含该字符，重新获取start位置
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            // 3. 获取子字符串长度： result  VS  end - start + 1
            result = Math.max(result, end - start + 1);
            // 4. 存储当前位置（end）的字符
            map.put(s.charAt(end), end + 1);
        }
        return result;
    }


    /**
     * https://github.com/zycR10/LeetcodeSolutions/blob/master/src/main/resource/LongestSubstringWithoutRepeatingCharacters.md
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring3(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int[] chars = new int[128];
        int max = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            l = Math.max(l, chars[s.charAt(r)]);
            max = Math.max(max, r - l + 1);
            chars[s.charAt(r)] = r + 1;
        }
        return max;
    }

}
